package 每日一题;

import java.util.ArrayList;
import java.util.List;

/**
 * 745. 前缀和后缀搜索
 * 设计一个包含一些单词的特殊词典，并能够通过前缀和后缀来检索单词。
 *
 * 实现 WordFilter 类：
 *
 * WordFilter(string[] words) 使用词典中的单词 words 初始化对象。
 * f(string pref, string suff) 返回词典中具有前缀 prefix 和后缀 suff 的单词的下标。如果存在不止一个满足要求的下标，返回其中 最大的下标 。如果不存在这样的单词，返回 -1 。
 *
 *
 * 示例：
 *
 * 输入
 * ["WordFilter", "f"]
 * [[["apple"]], ["a", "e"]]
 * 输出
 * [null, 0]
 * 解释
 * WordFilter wordFilter = new WordFilter(["apple"]);
 * wordFilter.f("a", "e"); // 返回 0 ，因为下标为 0 的单词：前缀 prefix = "a" 且 后缀 suff = "e" 。
 *
 * 提示：
 *
 * 1 <= words.length <= 104
 * 1 <= words[i].length <= 7
 * 1 <= pref.length, suff.length <= 7
 * words[i]、pref 和 suff 仅由小写英文字母组成
 * 最多对函数 f 执行 104 次调用
 */
public class D220714_T0745 {

    public static void main(String[] args) {

        WordFilter wordFilter = new WordFilter(new String[]{"apple"});
        wordFilter.f("a", "a");

    }

}

class PrefTree {
    List<Integer> index; //所有以当前的字母为前缀的 单词坐标
    PrefTree[] next;

    PrefTree(int index) {
        this.index = new ArrayList<>();
        this.index.add(index);
        next = new PrefTree[26];
    }

}

class WordFilter {

    PrefTree[] prefTree = new PrefTree[26];
    PrefTree[] suffTree = new PrefTree[26];

    public WordFilter(String[] words) {

        for (int i = 0; i < words.length; i++) {
            String word = words[i];
            insert(word, prefTree, i);
        }

        for (int i = 0; i < words.length; i++) {
            String word = words[i];
            insert(new StringBuilder(word).reverse().toString(), suffTree, i);
        }


    }

    public int f(String pref, String suff) {

        //开始查询前缀树
        PrefTree[] prefNext = prefTree;
        PrefTree[] suffNext = suffTree;
        List<Integer> prefList = new ArrayList<>();
        List<Integer> suffList = new ArrayList<>();
        for (int i = 0; i < pref.length(); i++) {

            if (prefNext[pref.charAt(i) - 'a'] == null) {
                return -1;
            }
            prefList = prefNext[pref.charAt(i) - 'a'].index;
            prefNext = prefNext[pref.charAt(i) - 'a'].next;

        }

        for (int i = suff.length() - 1; i >= 0; i--) {
            if (suffNext[suff.charAt(i) - 'a'] == null) {
                return -1;
            }
            suffList = suffNext[suff.charAt(i) - 'a'].index;
            suffNext = suffNext[suff.charAt(i) - 'a'].next;
        }

        int i = prefList.size() - 1;
        int j = suffList.size() - 1;
        while (i >= 0 && j >= 0) {
            if (prefList.get(i).equals(suffList.get(j))) {
                return prefList.get(i);
            } else if (prefList.get(i) > suffList.get(j)) {
                i--;
            } else j--;
        }
        return -1;

    }

    /**
     * 单词 插入字典树
     *
     * @param word 单词
     * @param next 字典树起始节点
     * @param i    当前单词的坐标
     */
    public void insert(String word, PrefTree[] next, int i) {

        for (int j = 0; j < word.length(); j++) {
            int charIndex = word.charAt(j) - 'a';
            if (next[charIndex] != null) {
                next[charIndex].index.add(i);
            } else {
                next[charIndex] = new PrefTree(i);
            }
            next = next[charIndex].next;
        }
    }

}
